package com.ruijixiang.leetcode.everyday.leetcode2025.leetcode202503;

import java.util.Arrays;

public class LeetCode20250302 {
    /**
     * 132.分割回文串 II：一个字符串s分割成一些子串，使每个子串都是回文串的最少分割次数
     * @param s
     * @return
     */
    public int minCut(String s){
        int n = s.length();
        if (n == 0) return 0;

        boolean[][] palindrome = new boolean[n][n];
        // Preprocess the palindrome table
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (i == j) {
                    palindrome[i][j] = true;
                } else if (i + 1 == j) {
                    palindrome[i][j] = (s.charAt(i) == s.charAt(j));
                } else {
                    palindrome[i][j] = (s.charAt(i) == s.charAt(j)) && palindrome[i + 1][j - 1];
                }
            }
        }

        // Dynamic programming to find minimum cuts
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = -1; // Base case: empty string

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                if (palindrome[j][i - 1]) {
                    dp[i] = Math.min(dp[i], dp[j] + 1);
                }
            }
        }

        return dp[n];
    }

    public static void main(String[] args){
        LeetCode20250302 leetCode20250302=new LeetCode20250302();
        String s="aab";
        System.out.println(leetCode20250302.minCut(s));
    }
}
